/**
题目:
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的 深拷贝。 
我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  null 。

思路:
    通过map 做指针的关联映射

效果:
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：3.5 MB, 在所有 Go 提交中击败了22.62%的用户
*/
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Next *Node
 *     Random *Node
 * }
 */

func copyRandomList(head *Node) *Node {
    m,cur := make(map[*Node]*Node,0),head
    for cur != nil{
        m[cur] = &Node{
            Val:cur.Val,
        }
        cur = cur.Next
    }
    cur = head
    for cur != nil{
        m[cur].Next = m[cur.Next]
        m[cur].Random = m[cur.Random]
        cur = cur.Next
    }
    return m[head]
}